680. Valid Palindrome II

題目：
Given a string s, return true if the s can be palindrome after deleting at most one character from it.
判斷一個字串 s 是否能在刪除最多一個字元的情況下變成回文

範例：

• Example 1:
  Input: s = "aba"
  Output: true
• Example 2:
  Input: s = "abca"
  Output: true
  Explanation: You could delete the character 'c'.
• Example 3:
  Input: s = "abc"
  Output: false

想法：
回文＝從左看或是從右看都長一樣
利用雙指標，『由左至右』＋『由右至左』檢查

程式碼：

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length()-1;
        //雙指標比較
        while(left < right){
            if(s.charAt(left) == s.charAt(right)){
                left++;
                right--;
            }else
            //遇到不相等——＞嘗試刪掉左邊或右邊
            return isPalindrome(s, left+1, right) || isPalindrome(s, left, right-1);
        }return true; //完全沒遇到不相等——＞是回文
    }
    //檢查 s[begin..end]是否是回文
    private boolean isPalindrome(String s, int begin, int end){
    while(begin < end){
        if(s.charAt(begin) != s.charAt(end)){
            return false;
        }
        begin++;
        end--;
    }
    return true;

實際操作：
索引：0 1 2 3 4
字元：d e e e e

STEP1 利用雙指標檢查前後是否相等
索引：0 4
字元：d e ——＞不相等所以利用isPalindrome檢查是否為回文

STEP2 刪掉一字元後檢查是否為回文
isPalindrome(s, left+1, right) ＝ isPalindrome(’deeee’, 1, 4)
索引：1 4
字元：e e ——＞相等所以回傳ture